//       John Broome           //
//                             //
//     Cs 331 Project 1        //
//                             //
//      Insertion Sort         //
//                             //
//   Sorts in ascending order  //
/////////////////////////////////

// Original code found in "Data Abstraction & Problem Soving with Java"
// 2005., Carrano, F., Prichard, J.

public class InsertionSort{
    
    public static void insertionSort(int[] theArray, int n) {
        
        
        for (int unsorted = 1; unsorted < n; unsorted++) {
            int nextItem = theArray[unsorted];
            int loc = unsorted;
            
            while (loc > 0 && theArray[loc-1] > nextItem) {
                
                // Shift the array to the right
                theArray[loc] = theArray[loc-1];
                loc--;
                
            }// end while
            
            theArray[loc] = nextItem;
            
        }// end for loop
        
    }//end main
    
    
}//end class